Packet-switching technologies concern the transport of packetized data segments across an interlinked data transport infrastructure including transport nodes and interconnecting links. The term Protocol Data Unit (PDU) will be used throughout the description presented herein, persons of ordinary skill in the art would recognize that the term refers generally to: cells, frames, packets, etc. Once a PDU is received at a switching node, the PDU is inspected, information is extracted from the PDU, and for switch processing purposes the PDU is referred to as a Switching Data Unit (SDU) corresponding to the PDU.
FIG. 1 is a schematic diagram showing a generic implementation of a switching node. In general terms the operation of a switching node 100 includes: receiving a PDU from an input port 102, storing 104 the corresponding SDU while the SDU is pending processing, determining 106 an output port 110 to send the PDU through, and forwarding 108 the PDU via the determined output port 110. It is understood that the ports of the switching node 100 include bi-directional ports which correspond to pairs of input ports 102 and output ports 110.
Packet-switching technologies from their infancy have largely concentrated on non-deterministic transport of PDUs. Benefits provided by the non-deterministic mode of transport are derived from an ability of transport nodes in a communications network to route PDUs around failed infrastructure.
The non-deterministic mode of transport suffers from an inherent inability to guarantee conveyance of PDUs. PDUs may be dropped in accordance with various PDU transport protocol specifications and error/congestion conditions. The inability to guarantee PDU conveyance is referred to as “best-effort transport”. Although packet-switched technologies, such as Asynchronous Transmission Mode (ATM) and MultiProtocol Label Switching (MPLS), providing support for deterministic PDU transport exist, best-effort non-deterministic packet-switched technologies enjoy the widest use.
There is an increasing demand for service level guarantees in provisioning services employing best-effort non-deterministic PDU transport technologies. One approach to provide service level guarantees, while still benefiting from non-deterministic PDU transport, is to ascribe traffic class associations to PDUs, and to preferentially process the corresponding SDUs, at network nodes in the transport path, based on the traffic class association. Only low priority SDUs and especially unclassified SDUs remain subject to best-effort processing and transport. Prioritizing SDU processing and transport intends to reduce denial of service instances to a minimum, and for this reason non-deterministic priority based SDU processing is preferred in certain applications.
In conveying “unicast” PDU traffic, each PDU traffic stream is generated by a source network node on edge and consumed by a sink network node on edge. “Multicast” traffic is generated by a single source network node on edge, replicated by an undetermined number of transport nodes in the interconnecting network, and aggregate traffic is consumed by multiple sink network nodes on edge. Therefore there is an unbound ability for the network to create traffic during a normal course of operation. Traffic creation in the network has numerous implications which are subject to intense current research and development some of which are addressed herein below.
Other service provisioning issues affecting resource utilization in the network relate to traffic patterns. Data traffic is not evenly distributed over the links and therefore processing requirements at network nodes differ. Data traffic created by source network nodes is in itself dynamic, unpredictable, and often bursty. Overall data traffic patterns vary from network to network and may even vary with time.
Further, electronic data services are typically provisioned from server network nodes to which a large amount of service request PDUs are directed, and from which a large amount of response PDUs are supplied.
In view of the above mentioned issues, the practical operation of a typical switching node must make provisions for queuing SDUs and adhere to queue service disciplines. Methods and apparatus for queuing SDUs pending processing, as well as methods of servicing queues continue to represent areas of intense research.
From the point of view of a particular switching node 100, the switching node 100 has multiple physical ports 102/110 via which PDUs are exchanged with the network. As the SDU traffic is conveyed through the switching node 100 in a non-deterministic fashion, multiple SDUs from a variety of input ports 102 may happen to be destined for to the same output port 110 within a short period of time, such is the case if the output port 110 is associated with a server node. Assuming equal port transport capacities and PDUs incoming at high rates close to the full link transport bandwidth, a number of SDUs have to be held in an output port queue 112 for forwarding via the output port 110. SDUs stored in the output port queue 112 incur a processing latency and depart from the queue 112 when the output port 110 is ready to transmit.
Should a multicast PDU be received at the switching node 100, the replication of the corresponding SDU and the individual forwarding of each replica is yet another factor which may also delay the processing of other SDUs. The processing of SDUs is therefore affected by queuing methods and queue service disciplines employed.
A prior art U.S. Pat. No. 6,212,182 entitled “Combined Unicast and Multicast Scheduling” which issued on Apr. 3, 2001, to McKeown describes a complex queuing method for preprocessing received ATM cells. For all cells received via an input port, unicast cells are queued in a group of unicast output port queues associated with the input port, and multicast cells are queued in a multicast queue associated with the input port. The intended ATM application benefits from this complex cell separation. Further McKeown describes an improved request-based scheduling of the separated unicast/multicast cell traffic to effect cell transfer across a switching fabric. Although inventive, the described methods assume reliance on prior reservation of transport and processing bandwidth enforceable in using ATM technologies, addresses global queuing issues only and does not address issues related to output queuing requirements which do not seem to represent a concern.
Processing queues may be implemented in a variety of ways between which, the use of physical First-In/First-Out queues (FIFOs) and link list queuing have enjoyed extensive research and implementation.
A prior art U.S. Pat. No. 6,349,097 entitled “Multicasting in Switching Apparatus” which issued Feb. 19, 2002 to Smith makes use of global FIFO queues to store unicast and multicast ATM cells so that the received sequence of the cell stream can be retained. The solution is concerned with solving quality-of-service issues related to cell sequencing. Smith also does not address output port queuing resource utilization issues.
Physical handling of received SDUs by transferring them between input ports 102, various buffers 120, various queues 112, output port(s) 110, etc. has drawbacks related to the fact that read and write operations are time consuming. Except for ATM cell processing, where cells have a fixed size, it is hard to contain the amount of time spent on physical SDU transfers within a switching node 110.
As the SDUs have to be stored at switching nodes 100 pending processing, it is best if the physical handling of each SDU was reduced preferably to one write operation when received, and preferably to at least one read operation when the destination port(s) 110 is/are ready to transmit the PDU out. For these and other reasons using centralized SDU storage 120 is preferred.
At all other times, structures called “descriptors”, comparatively smaller than SDUs, are used to track SDU attributes. These attributes may include diverse information used to determine an output port 110 to send the SDU through and information to prioritize the forwarding of the SDU.
In view of the above, methods of queuing SDUs become in effect methods of queuing SDU descriptors. SDU descriptors may therefore be physically stored in physical FIFO queues 112. Descriptor FIFO queuing implementations are comparatively simple and more adapted to hardware implementation. Multicast SDUs are simply handled by replicating the multicast SDU descriptor and the resulting multiple descriptors are stored in corresponding output queues 112 associated with corresponding destination ports 110.
Although SDU descriptors are small compared with corresponding SDU sizes, requirements for high integration, high port density per switch, and high throughput capacity, lead to a need to address issues related to SDU descriptor storage in FIFO queues 112. The processing of multicast SDUs compounds the descriptor storage problem.
Consider the above mentioned scenario in which, a switching node 100, implementing SDU descriptor FIFO output port queuing, provides interconnectivity in a client-server networking environment. Assuming same capacity ports 102/110, the output port 110 associated with the server node, will typically experience congestion as the aggregate traffic from all other input ports 102 is directed to the server node.
Worse case scenario switching node design calls for the descriptor FIFO queue 112 associated with the server port 110 to be large (long) enough to accommodate SDU descriptors associated with an expected number of SDUs during a typical burst of server requests. Without knowing which output port 110 will be associated with the server during the manufacturing of the switching node 100, all output ports 110 need be provided with enough storage resources (112) in accordance with the worse case scenario. As port (102/110) density per switching node 100 increases, the storage reservation requirements for descriptor FIFO queues 112 increases also. If provisions for prioritization of SDU processing are to be made, the aggregate descriptor storage reservation requirements need be multiplied by the number of priority levels supported per port.
Size limitations on FIFO queue implementations exist because exclusive FIFO queue reservations are necessary. The total number of reserved FIFO queue descriptor entry “slots” is usually several times the maximum number of SDUs that can be processed at a switching node. In accordance with a typical implementation, suppose that the switching node having a typical number of 16 ports 102/110 has a combined storage capacity to buffer 1000 PDUs. With a single output port queue 112 per output port 110, typically 500 SDU descriptor slots are reserved for each FIFO queue 112. Therefore a total amount of storage for 8000 descriptor entries must be provided.
Complex switching node implementations accommodating a large number of SDUs in a central storage and/or implementing sophisticated transmit prioritization schemes use linked list queuing in an attempt to alleviate descriptor storage issues.
Link list queue implementations include interlinking SDU descriptors stored centrally in shared storage, via SDU descriptor pointers, in link lists defining virtual queues. Storage efficiency is enjoyed in making use of shared storage to hold SDU descriptors. Each SDU descriptor contains at least one next SDU descriptor pointer. SDU descriptor pointers require even less storage space than SDU descriptors.
Considering the above mentioned exemplary setup implementing a linked list queuing in a unicast only environment, for 1000 unicast PDUs buffered at the switching node, storage for only 1000 descriptor entries needs to be provided as which is significantly less than 8000. Each of the 1000 descriptors used in linked list queuing have only marginally larger storage requirements to account for the additional descriptor pointer storage. For each of the 16 output ports 110 only a single pointer register is needed to hold the head of line pointer specification for each linked list queue 112.
Although storage resource utilization reductions are achieved by using linked list queuing implementations for unicast traffic, the use of linked lists for queue implementations is cumbersome in handling multicast SDU queuing. FIG. 2 is exemplary of a typical association between unicast and multicast SDUs pending forwarding via a group of ports. Multicast SDUs cause a multiple-to-one and/or a one-to-multiple fan-out across multiple queues 112. As shown, each multicast SDU may have a different fan-out diversity across the port queues which makes for a complex combined association structure.
An implementation attempting to address this association complexity is illustrated in FIG. 3 which shows a global linked structure for unicast and multicast SDU queuing at a multi-port switching node. The implementation calls for the use of multiple SDU pointer fields associated with each multicast SDU linked list entry.
Each multicast SDU entry has a number of pointer fields equal to the maximum possible fan-out (the total number of ports of the switching node minus one—the port on which the corresponding multicast PDU was received). In accordance with a worst case scenario, for each multicast SDU, N-1 linking operations need to be performed within one SDU processing time interval. Such a task would be hard to achieve for high port density implementations. The processing of multicast SDUs further negatively impacts the operation of a switching node because the processing of multicast SDUs is memory access intensive. With a limited memory access bandwidth, uncontrolled processing multicast SDUs is detrimental to unicast SDU processing.
In provisioning support for Virtual Local Area Network (VLAN) or any other multicast domain control provisioning, multicast SDUs have a very diverse output port fan-out, the number of output ports being substantially less than the total number of ports per switching node. The high likelihood of the diversity of the fan-out being substantially less than the total number of ports, enables implementation of high port density designs. The discrepancy between a large number of ports per switching node and the median fan-out diversity leads to a lot of the descriptor pointer fields associated with multicast SDU entries to remain unused (filled with NULL pointers). At high multicast SDU throughput, unused descriptor pointer fields can take up a lot of storage resources and a lot of processing overhead is incurred in scheduling SDU processing based on the complex associativity structure. This represents a major disadvantage in using linked list implementations to queue multicast SDUs leading to a storage space utilization inefficiency wasting SDU processing resources and bandwidth.
There therefore is a need to solve the above mentioned issues in providing queuing methods and queue service disciplines for combined unicast and multicast SDU traffic processed at a switching node.